package ErChaShu;


import java.util.Arrays;

public class BinSeqTree implements BinTree {
    // 顺序存储结构: 数组
    private int[] elements;
    // 顺序二叉树最大存储空间
    private int size;
    // 当前最大存放位置下标
    private int currentIndex;

    /**
     * 限定最大存储容量的初始化方法
     *
     * @param size 二叉树最大存储容量
     */
    public BinSeqTree(int size) {
        this.size = size;
        this.elements = new int[size];
        this.currentIndex = 0;
    }

    /**
     * 通过已知数组创建顺序二叉树
     *
     * @param data
     */
    public BinSeqTree(int[] data) {
        this.size = data.length;
        this.elements = data;
        this.currentIndex = data.length - 1;
    }

    @Override
    //插入数据
    public boolean insert(int data) {
        //通过对当前数组下标和二叉树最大容量作比较判断二叉树是否为满
        if (this.currentIndex >= this.size) {
            //如果为满则输出"Tree is full"，并返回false
            System.out.println("Tree is full");
            return false;
        }
        //如果二叉树不为满则继续执行
        //将数据存储到数组当前下标位置中，并将下标自增
        this.elements[this.currentIndex++] = data;
        //返回true
        return true;
    }

    @Override
    //获得当前结点的双亲结点
    public Integer getParent(int index) {
        //当索引为0的时候，就肯定是根节点，根节点没有双亲则返回null
        //当索引大于等于树的大小的时候，就说明越界了，也返回null
        //所以这是在判断传入参数的合法性
        if (index == 0 || index >= this.size) {
            return null;
        }
        // 二叉树性质运用
        //基于数组的二叉树顺序存储结构中，计算父节点索引使用 (index - 1) / 2（向下取整）
        int parentIndex = (index - 1) / 2;
        //问题：为什么这里是(i-1)/2而书上是i/2？
        //解答：？
        //返回当前结点的双亲结点
        return this.elements[parentIndex];
    }

    @Override
    //获取当前结点的左孩子
    public Integer getLeftChild(int index) {
        //已知双亲结点的下标为index，左孩子的下标为2*index+1
        int leftChildIndex = 2 * index + 1;
        //检查当前左孩子索引的合法性
        //当当前结点左孩子的下标小于我们总结点数（否则数组越界）
        //并且当前结点左孩子不为空则合法
        if (leftChildIndex < this.size && this.elements[leftChildIndex] != 0) {
            //合法则返回当前结点的左孩子
            return this.elements[leftChildIndex];
        }
        //否则则返回空
        return null;
    }

    @Override
    //获得当前结点的右孩子
    public Integer getRightChild(int index) {
        //已知当前结点下标为index那么它的右孩子下标应该为2*index+2
        int rightChildIndex = 2 * index + 2;
        //判断当前结点右孩子的合法性
        //当当前节点右孩子的下标小于总结点数（不小于则数组越界）
        //并且当前结点的右孩子不为空则合法
        if (rightChildIndex < this.size && this.elements[rightChildIndex] != 0) {
            //合法则返回当前结点右孩子
            return this.elements[rightChildIndex];
        }
        //否则返回空
        return null;
    }

    @Override
    public void display() {
        // 输出顺序二叉树存储空间原始数据
        System.out.println(Arrays.toString(this.elements));
        // 打印每一个元素的详细信息（元素自身下标、双亲节点、左孩子节点、右孩子节点）
        for (int i = 0; i < this.size; i++) {
            if (this.elements[i] != 0) {
                System.out.print("Index " + i + ": Value " + this.elements[i]);
                System.out.print(", Parent: " + getParent(i));
                System.out.print(", Left Child: " + getLeftChild(i));
                System.out.print(", Right Child: " + getRightChild(i));
                System.out.println();
            }
        }
    }

    @Override
    public void preOrderTraversal() {
        System.out.println("先序遍历:");
        preOrderTraversalHelper(0);
        System.out.println();
    }

    private void preOrderTraversalHelper(int index) {
        if (index < 0 || index >= this.size || this.elements[index] == 0) {
            return;
        }
        // 第一步访问根节点
        System.out.print(this.elements[index] + " ");
        // 计算左子树根节点下标
        int leftChildIndex = 2 * index + 1;
        // 计算右子树根节点下标
        int rightChildIndex = 2 * index + 2;
        // 先序遍历左子树
        preOrderTraversalHelper(leftChildIndex);
        // 先序遍历右子树
        preOrderTraversalHelper(rightChildIndex);
    }

    @Override
    public void inOrderTraversal() {
        System.out.println("中序遍历:");
        inOrderTraversalHelper(0);
        System.out.println();
    }

    private void inOrderTraversalHelper(int index) {
        if (index < 0 || index >= this.size || this.elements[index] == 0) {
            return;
        }
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        inOrderTraversalHelper(leftChildIndex);
        System.out.print(this.elements[index] + " ");
        inOrderTraversalHelper(rightChildIndex);
    }

    @Override
    public void postOrderTraversal() {
        System.out.println("后序遍历:");
        postOrderTraversalHelper(0);
        System.out.println();
    }

    private void postOrderTraversalHelper(int index) {
        if (index < 0 || index >= this.size || this.elements[index] == 0) {
            return;
        }
        int leftChildIndex = 2 * index + 1;
        int rightChildIndex = 2 * index + 2;
        postOrderTraversalHelper(leftChildIndex);
        postOrderTraversalHelper(rightChildIndex);
        System.out.print(this.elements[index] + " ");
    }
}

